package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.ArrayUtils;

import java.io.PipedWriter;

public class Day26_2 {

    /****
     * 向按个位，再按十位 ，再按百位。。。。
     *
     * @param arr
     */
    public static void bucketSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int max = ArrayUtils.findMax(arr);
        //有多少位就需要进出桶多少次
        int digit = digitOf(max);
        int[] bucket = new int[arr.length];
        int radix = 10;
        int j = 0;
        int r = arr.length-1;
        int l = 0;
        int i = 0;
        for (int d = 1; d <= digit; d++) {
            int[] count = new int[radix];
            for (i = l; i <= r; i++) {
                j = numInDigit(arr[i], d);
                count[j]++;
            }
            for (i = 1; i < radix; i++) {
                count[i] += count[i - 1];
            }
            for (i = r; i >= l; i--) {
                j = numInDigit(arr[i], d);
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }
            for (i = l, j = 0; i <= r; i++, j++) {
                arr[i] = bucket[j];
            }
        }
    }

    private static int digitOf(int num) {
        int digit = 1;
        //1000 ->100
        while (num / 10 != 0) {
            digit++;
            num = num / 10;
        }
        return digit;
    }

    private static int numInDigit(int num, int digit) {
        int pow = (int) Math.pow(10, digit - 1);
        return ((num / pow) % 10);
    }

    private static int maxBits(int[] arr) {
        int max = ArrayUtils.findMax(arr);
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] ints = {12, 1, 12, 323, 45, 8};
        bucketSort(ints);
        ArrayUtils.print(ints);
    }

}
